1. Field of the Invention
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to techniques for generating memory efficient technology libraries used for timing and power estimations.
2. Related Art
An electronic design automation (EDA) system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes (elements) and edges, e.g., connections between nodes, and can be represented using a directed cyclic graph structure having nodes which are connected to each other with signal lines. A single node can have multiple fan-ins and multiple fan-outs. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device.
The design flow for the design of integrated circuits (e.g., ASIC, microprocessors, microcontrollers, etc.) requires several descriptions of the design library that are used as input to different CAD tools. For instance, a synthesis library is typically required. The main loop in the IC design environment consists of describing the IC design in terms of primitive models from the synthesis library, verifying (e.g., functionality, power and timing constraints, etc.) through various verification techniques and then refining and correcting the IC design. During this process, timing and power estimations or (xe2x80x9csimulationsxe2x80x9d) are often performed by the computer system to optimize the IC design and to determine if the overall circuit design is maintaining prescribed timing and power constraints.
FIG. 1 illustrates an example library cell 10. Within a technology library, each signal path of a library cell 10 can have its own timing model. For instance, for cell 10, a first path from input 12 to output 30 can have one timing model while a second path from input 16 to output 30 can have a second timing model. The timing delay (or other constraint) through a path from one input to an output is called a timing arc. Library cell 10 has at least four timing arcs. A timing arc is modeled based on a function of two variables, usually the input transition rate and the output capacitance load. Originally, timing models for timing arcs were based on fixed-form linear equations of output capacitance load. Later, these timing models (e.g., for generic CMOS) were based on a linear equation including both of these two input variables (with fixed coefficients) and, similarly, the same linear equation form was used to model all of the gates of a given technology library. Although the linear equation form was the same for all gates, the coefficients of the linear equation could change from timing arc to timing arc within the same technology library. This allowed the timing calculations to be generalized across the entire technology library and thereby made the timing calculations easier to perform. However, the calculations were not entirely accurate because some library gates were not well modeled by the fixed-form linear equation. It is desired to provide a more accurate method for providing timing delay estimations within an EDA system.
To improve accuracy, piecewise linear analysis was introduced to simulation and this provided a linear representation in each region but used a two dimensional representation. Three dimensional (3-D) non-linear look-up tables were then introduced that used bilinear equations for interpolation within the data points of the table. Using this prior art modeling method, each timing arc of a technology library is represented by a separate look-up table. Each point of a look-up table is referenced by an input transition rate and an output capacitance load and represents a delay value. Interpolation and extrapolation functions are used to determine values in between the given data points. FIG. 2A illustrates an original look-up table provided by the user. FIG. 2B illustrates the interpolated results of FIG. 2A showing the accuracy of a look-up table approach particularly for tables with xe2x80x9cabnormalxe2x80x9d data, such as the data at the upper right corner of FIG. 2A.
Although look-up tables, like the ones shown in FIG. 2A and FIG. 2B, provide very accurate timing and power simulations, they unfortunately also consume relatively large amounts of memory resources within an EDA system as one technology library can contain as many as tens of thousands of look-up tables. For instance, each timing arc of each library cell can require its own individual look-up table data structure. Assuming each look-up table is 5xc3x975 (e.g., consuming about 1.0 K bytes each) and assuming further that some technology libraries have over 1,000 cells per library, there can be between 5,000 and 20,000 look-up tables per technology library. Because multiple timing arcs can exist within each library cell, a single cell can require as much as 5-20 K bytes of memory storage for look-up tables. At this number, between 5.0 M bytes and 20.0 M bytes of memory can be required to provide delay data for a typical technology library. Further, large look-up table sizes slow down timing calculations. Because technology libraries are approaching 2,000 cells and further because users demand that design tools be able to deal with multiple different operating conditions (each of which requires a different set of timing data), it is desired to provide a more memory efficient method for providing timing delay estimations within an EDA system.
Accordingly, what is needed is a system and method for modeling the timing and/or the power for cells of a netlist that is memory efficient. Furthermore, what is needed is a system and method for accurately modeling the timing and/or power of cells of a netlist. In view of the above needs, the present invention provides a system and method for increasing the efficiency of an IC design process to thereby provide a faster, more cost effective and more accurate IC design process. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.
A system and are described herein for using scalable polynomials to translate a look-up table delay model into a memory efficient scalable polynomial-based model. The present invention recognizes that a set of scalable polynomials can effectively and efficiently be used to represent the timing and power information contained within the look-up tables of a technology library. The present invention allows each timing arc to have a different scalable polynomial thereby increasing timing calculation accuracy. Further, reducing look-up table models into polynomial models significantly reduces memory usage requirements and increases computation speed. The system of the present invention receives an input library of predefined cells having a number of predefined look-up tables for modeling the timing arcs of the cells. The look-up tables characterize the timing through the timing arcs of each of the cells of the input library. Each look-up table is referenced by two input variables (e.g., input transition rate and output load capacitance) which correspond to an output delay time through the timing arc.
The present invention analyzes each memory inefficient look-up table and selects a polynomial form (of two variables) for representing the timing data of the look-up table. The polynomial form is selected from a set of scalable polynomial systems (e.g., the decomposed Taylor Series and the Joint Taylor Series). The polynomial forms that are selected can have different orders (e.g., first, second, third, etc.) with respect to the input variables. For input look-up tables of a threshold size and smaller, an exhaustive process is used whereby polynomials are first selected with small orders and gradually larger orders are selected until an appropriate polynomial form is determined. For larger look-up tables, the selection of the polynomial order is first based on numerical differences.
For a particular selected polynomial form, the present invention performs a linear least square error (LSE) curve fitting analysis thereon to determine the proper set of coefficients for the selected polynomial form. The selected polynomial with coefficients is then accepted or rejected based on a Chi-Square analysis that is performed on the selected polynomial to avoid problems associated with oscillations due to over-fitting. If accepted, the memory efficient polynomial replaces the input look-up table and is stored in the technology library and subsequently used for timing calculation. If rejected, a next polynomial form is selected and processing is re-done. If no acceptable polynomial form can be found, the input look-up table is not replaced. By allowing different polynomial forms to represent the look-up tables, the present invention provides excellent timing accuracy for most library cells (e.g., five percent error or less) while reducing memory consumption by as much as 94 percent. The embodiments of the present invention are equally well suited for timing and power related computations.
Specifically, an embodiment of the present invention includes a computer implemented method comprising the steps of: a) accessing from memory a look-up table data structure for a cell, the look-up table data structure having timing data points each referenced by first and second input variables; b) translating the look-up table data structure into a selected polynomial form having a selected order and a set of coefficients and further having, as input variables, the input transition rate and the output load capacitance, wherein the selected polynomial form is selected out of a predetermined set of scalable polynomial forms; c) in the memory, replacing the look-up table data structure with the selected polynomial form; d) repeating steps a)-c) for a plurality of cells of a technology library stored in the memory; and e) using the selected polynomial forms to estimate timing delays through timing arcs of the plurality of cells of the technology library.
Embodiments include the above and wherein the first input variable is an input transition rate of an input of the cell and wherein the second input variable is an output load capacitance of an output of the cell and wherein the step b) comprises the steps of: b1) out of the predetermined set of scalable polynomial forms, selecting a first polynomial form of a first selected order, the first polynomial form having a first set of coefficients; b2) determining values for the first set of coefficients by performing a linear least square error curve fitting computation on the timing data points with respect to the first polynomial form; b3) performing a Chi-Square computation with respect to the timing data points and the first polynomial form including the values determined at step b2) to obtain a Chi-Square result; b4) accepting the first polynomial form including the values determined at step b2) provided the Chi-Square result is greater than a given threshold; and b5) provided the Chi-Square result is not greater than the given threshold, repeating steps b2)-b4) with respect to a second polynomial form having a second selected order and a second set of coefficients, wherein the second polynomial form is selected out of the predetermined set of scalable polynomial forms.